package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

public class Q_数组中的第K个最大元素 {
    public static void main(String[] args) {
        // Q_数组中的第K个最大元素 exe = new Q_数组中的第K个最大元素();
        // int[] nums = {303, -951, 303, -9};
        // int[] copy = Arrays.copyOf(nums, nums.length);
        // Arrays.sort(copy);
        // Tools.printArray(copy);
        // // int[] nums = {23, 1};
        // System.out.println(exe.findKthLargest_2(nums, 2));


        judge();
    }

    private static void judge() {
        Q_数组中的第K个最大元素 exe = new Q_数组中的第K个最大元素();
        Random rd = new Random(1234);
        int MAX_LEN = 5;
        int LOOP_CNT = 1000;
        int eqnum = 0;
        for (int i = 0; i < LOOP_CNT; i++) {
            int[] originNums = RandomUtil.randomArray(rd.nextInt(MAX_LEN)+1, -1000, 1000);
            int k = rd.nextInt(originNums.length)+1;
            int r1 = exe.findKthLargest_1(Arrays.copyOf(originNums, originNums.length), k);
            int r2 = exe.findKthLargest_2(Arrays.copyOf(originNums, originNums.length), k);
            if (r1 != r2) {
                System.out.println("xxxxxxxxxxxxxxxxxxxxxx");
                System.out.println(r1);
                System.out.println(r2);
                System.out.println("k="+k);
                Tools.printArray(originNums);
                System.out.println("EQ COUNT: " + eqnum);
                break;
            } else {
                eqnum++;
            }
        }

        System.out.println("!!!!!!!!!!!!!!!!!!!!!!!");
    }


    /**
     * M1: 小顶堆
     * */
    public int findKthLargest_1(int[] nums, int k) {

        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        for (int num : nums) {
            if (heap.size()<k) {
                heap.add(num);
            } else {
                // 打擂
                Integer peek = heap.peek();
                if (num > peek) {
                    heap.poll();
                    heap.add(num);
                }
            }
        }

        return heap.isEmpty() ? -1 : heap.peek();
    }

    /**
     * M2: 荷兰国旗方式
     */
    public int findKthLargest_2(int[] nums, int k) {
        return find(nums, k, 0, nums.length - 1);
    }

    public int find(int[] nums, int k, int left, int right) {
        while (left <= right) {
            int l = left, r = right;
            int p = l + (int) (Math.random()*(r-l+1)); // !! 注意运算优先级, 整体计算好在转int
            int pivot = nums[p]; // !! 注意运算优先级, 整体计算好在转int; !! 取出值, 该位值会改变的.
            for (int i = l; i <= r;) { // !! 包含=, 最后和自己位置互换后, r搞好指向最后的相等元素
                if (nums[i] > pivot) { // 红色
                    swap(nums, i, l++);
                    i++;
                } else if (nums[i] < pivot) { // 蓝色
                    swap(nums, i, r--);
                } else { // 白色
                    i++;
                }
            }

            // 1) k-1 落在之间, 就是 pivot位值; 2) 左; 3) 右.
            if (k - 1 < l) {
                right = l-1;
            } else if (k - 1 > r) {
                left = r+1;
            } else {
                return pivot;
            }
        }

        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
